package org.example;

import java.util.HashMap;

public class Solution12 {

    public String minWindow(String s, String t) {
        // 检查输入的合法性
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 创建哈希表，存储t中每个字符出现的次数
        HashMap<Character, Integer> hashMapT = new HashMap<>();
        for (char c : t.toCharArray()) {
            hashMapT.put(c, hashMapT.getOrDefault(c, 0) + 1);
        }

        // 当前窗口内的字符和数量
        HashMap<Character, Integer> window = new HashMap<>();

        // 滑动窗口的边界
        int left = 0, right = 0;

        // 已经匹配的字符数量
        int formed = 0;

        // 存储答案的数组，-1表示未找到，起始索引，结束索引
        int[] answer = {-1, 0 , 0};

        while (right < s.length()) {
            char c = s.charAt(right);

            // 更新当前窗口内的字符数量
            window.put(c, window.getOrDefault(c, 0) + 1);

            // 如果当前字符是目标中需要的，并且数量满足需求
            if (hashMapT.containsKey(c) && window.get(c).intValue() == hashMapT.get(c).intValue()) {
                formed++;
            }

            // 尝试收缩窗口
            while (left <= right && formed == hashMapT.size()) {
                c = s.charAt(left);

                // answer[0] == -1 没有找到符合条件的子串
                // right - left + 1 < answer[0] 当前窗口的长度小于已记录的最短子串长度
                if (answer[0] == -1 || right - left + 1 < answer[0]) {
                    answer[0] = right - left + 1;
                    answer[1] = left;
                    answer[2] = right;
                }

                // 减少当前窗口的字符数量
                window.put(c, window.get(c) - 1);

                // 窗口不满足了，要减
                if (hashMapT.containsKey(c) && window.get(c) < hashMapT.get(c)) {
                    formed--;
                }

                left++;
            }

            // 移动右指针
            right++;
        }

        return answer[0] == -1 ? "" : s.substring(answer[1], answer[2] + 1);

    }

}
